package com.base.dynamicprograming;

import java.util.Arrays;

/**
 * @ClassName: CoinChange
 * @Description: 经典动态规划问题，322. 零钱兑换
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 * <p>
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 * <p>
 * 你可以认为每种硬币的数量是无限的。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/coin-change
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author: li
 * @Date: 2021/8/19 8:16 下午
 */
public class CoinChange {
    public int coinChange(int[] coins, int amount) {
        /**
         * 自上而下的动态规划+递归
         */

        int[] dpArray = new int[amount + 1];

        return dp(coins, amount, dpArray);
    }

    public int dp(int[] coins, int amount, int[] dp) {
        if (amount == 0) {
            return amount;
        }
        if (amount < 0) {
            return -1;
        }
        if (dp[amount] != 0) {
            return dp[amount];
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < coins.length; i++) {
            int sub = dp(coins, amount - coins[i], dp);
            if (sub == -1) {
                //子问题无解，跳过
                continue;
            }
            res = Math.min(res, 1 + sub);
        }
        dp[amount] = res == Integer.MAX_VALUE ? -1 : res;
        return dp[amount];
    }

    public int coinChange1(int[] coins, int amount) {
        /**
         * 自底向上动态规划+迭代。
         */


        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i < coins[j]) {
                    continue;
                }
                dp[i] = Math.min(dp[i], 1 + dp[i - coins[j]]);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];

    }
}
